754D - Fedor and coupons - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

int n, k, l[300001], r[300001];

vector <pair <int, long long>> v;
bool possible (long long len) {
    v.clear();

    for (int i = 1; i <= n; ++ i) {
        if (r[i] - len + 1 < l[i]) {
            continue;
        }
        
        v.push_back ({l[i], 0});
        v.push_back ({r[i] - len + 2, 1});
    }

    sort (v.begin(), v.end());

    int sum = 0;
    for (int i = 0; i < (int)v.size() - 1; ++ i) {
        if (v[i].second) {
            -- sum;
        } else {
            ++ sum;
        }
        
        if (v[i].first != v[i + 1].first) {
            if (sum >= k) {
                return true;
            }
        }
    }

    return false;
}

void result (long long len) {
    cout << len << "\n";
    
    map <int, int> mp;

    for (int i = 1; i <= n; ++ i) {
        if (r[i] - len + 1 < l[i]) {
            continue;
        }

        mp[l[i]] ++;
        mp[r[i] - len + 2] --;
    }

    int sum = 0;
    int id = -1;

    for (auto it : mp) {
        sum += it.second;

        if (sum >= k) {
            id = it.first;
            break;
        }
    }

    if (id == -1) {
        for (int i = 1; i <= k; ++ i) {
            cout << i << " ";
        }
        cout << "\n";
        exit(0);
    }

    for (int i = 1; i <= n && k; ++ i) {
        if (l[i] <= id && id <= r[i] - len + 2) {
            cout << i << " ";
            -- k;
        }
    }

    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; ++ i) {
        cin >> l[i] >> r[i];
    }

    long long l = 0, r = 2e9 + 1;
    while (l < r) {
        long long mid = (l + r + 1) >> 1;

        if (possible (mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }

    result (l);

    return 0;
}/*1690054665.6251605*/